//Grid min
//$Id: gridmin.h 441 2010-04-09 17:27:20Z Oleg.Bulychov $
#pragma once

#include "src/heo/include/lf_endl.h"
#include "src/heo/include/random.h"
#include "src/heo/include/reflection.h"
#include "src/heo/include/solution.h"
#include "src/heo/include/optimization_direction.h"
#include "src/heo/include/transmit_vector.h"
#include <set>


typedef std::vector<size_t>    IntVector;
typedef std::vector<IntVector> IntMatrix;
typedef std::set<size_t>       IntSet;  


bool operator ==(const IntMatrix& left, const IntMatrix& right)
{
    for (size_t i = 0; i < left.size(); ++i)
        for (size_t j = 0; j < left[i].size(); ++j)
            if (left[i][j] != right[i][j])
                return false;

    return true;
}


class Grid
{
    //DISALLOW_COPY_AND_ASSIGN(Grid);
protected:
    IntSet rows_, columns_;
public:

    explicit Grid() {};
    ~Grid() {};

    size_t size() { return rows_.size()*columns_.size(); }

    IntSet& get_Rows() { return rows_; }
    IntSet& get_Columns() { return columns_; }

    void set_Rows(const IntSet& t)
    {
        IntSet::const_iterator iter;
        for (iter = t.begin(); iter != t.end(); ++iter)
            rows_.insert(*iter);
    }

    void set_Columns(const IntSet& t)
    {
        IntSet::const_iterator iter;
        for (iter = t.begin(); iter != t.end(); ++iter)
            columns_.insert(*iter);
    }

    void print(std::ostream& os)
    {
        IntSet::const_iterator iter;
        os << "[";
        for (iter = rows_.begin(); iter != rows_.end(); ++iter)
            os << " " << *iter+1;
        os << " ] x ["; 
        for (iter = columns_.begin(); iter != columns_.end(); ++iter)
            os << " " << *iter+1;
        os << " ]" << lf;
    }
};


bool operator <=(const IntSet& left, const IntSet& right)
{
    IntSet::const_iterator iter;

    if (left.size() > right.size()) 
        return false;

    for (iter = left.begin(); iter != left.end(); ++iter) // left \subset right ?
        if (right.find(*iter) == right.end()) 
            return false;

    return true; // left = right
}


bool operator <=(Grid& left, Grid& right)
{
    return (left.get_Rows() <= right.get_Rows()) && (left.get_Columns() <= right.get_Columns());
}


struct GridMin_Config
{
    size_t  limit_output_;

    static char const* get_Name() { return "gridmin"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(limit_output),               20);
    }
};
//__________________________________________________________________________________
typedef std::vector<Grid> GridVector;

struct GridMin_Problem
{
    size_t m_, n_, seed_, allow_dup_, k_;
    double density_;
    IntMatrix  rel_;
    GridVector grids_;

    explicit GridMin_Problem()
    {}

    static char const* get_Default_File_Name() { return "foo.bar"; }

    template<class I, class E>
    bool read(I& in, E* env, uniform_random& rnd)
    {
        std::string s;
        size_t t;

        in >> s;
        if (s != "matrix")
            return false;

        in >> m_ >> n_;
        if (m_ < 1 || n_ < 1)
            return false;

        in >> density_;
        if (density_ < 0 || density_ > 1)
            return false;

        in >> seed_ >> allow_dup_;

        rel_.resize(m_); 
        for (size_t i = 0; i < m_; ++i)
            rel_[i].resize(n_);

        for (size_t i = 0; i < m_; ++i)
            for (size_t j = 0; j < n_; ++j)
            {
                in >> t;
                if (t < 0 || t > 1)
                    return false;
                else
                    rel_[i][j] = t;
            }

            in >> s;
            if (s != "grids")
                return false;

            in >> k_;
            if (k_ < 0)
                return false;

            grids_.resize(k_);

            for (size_t i = 0; i < k_; ++i)
            {
                IntSet r, c;

                for (;;)
                {
                    in >> t;
                    if (t > 0)
                        r.insert(t - 1);
                    else if (t == 0) 
                        break;
                    else
                        return false;
                }

                for (;;)
                {
                    in >> t;
                    if (t > 0)
                        c.insert(t - 1);
                    else if (t == 0) 
                        break;
                    else
                        return false;
                }

                grids_[i].set_Rows(r);
                grids_[i].set_Columns(c);
            }

            print(std::cout, env);

            return true;
    }

    template<class E>
    void print(std::ostream& os, E* env)
    {
        os << "#-relation:" << lf; 
        for (size_t i = 0; i < m_; ++i)
        {
            for (size_t j = 0; j < n_; ++j)
                os << rel_[i][j] << " ";
            os << lf;
        }

        os << lf;

        std::cout << "Gids (" << grids_.size() << "):" << lf;
        for (GridVector::iterator iter = grids_.begin(); iter != grids_.end(); ++iter)
            (*iter).print(os);
        std::cout << lf;
    }
};
//__________________________________________________________________________________
//__________________________________________________________________________________
class GridMin_Solution
{
    //DISALLOW_COPY_AND_ASSIGN(GridMin_Solution);
public:
    typedef int            TCostType;
    typedef minimization<TCostType> TDirection;
protected:
    TCostType    cost_;
    bool         changed_;
    IntMatrix    hits_;
    IntVector    grids_set_;
public:
    explicit GridMin_Solution(): cost_(0), changed_(false)
    {}

    ~GridMin_Solution()
    {
    }

    template<class E>
    void init(E* env, uniform_random& rnd)
    {
        hits_.resize(env->problem_.rel_.size()); 
        for (size_t i = 0; i < hits_.size(); ++i)
            hits_[i].resize(env->problem_.rel_[i].size(), 0);

        grids_set_.resize(env->problem_.grids_.size(), 0);
    }


    template<class E>
    void inc_Hits(E* env, size_t i)
    {
        IntSet::const_iterator ir, ic, 
            irb = env->problem_.grids_[i].get_Rows().begin(),
            ire = env->problem_.grids_[i].get_Rows().end(),
            icb = env->problem_.grids_[i].get_Columns().begin(),
            ice = env->problem_.grids_[i].get_Columns().end();

        for (ir = irb; ir != ire; ++ir)
            for (ic = icb; ic != ice; ++ic)
                hits_[*ir][*ic] += 1;
    }

    template<class E>
    bool dec_Hits(E* env, size_t i)
    {
        IntSet::const_iterator ir, ic, 
            irb = env->problem_.grids_[i].get_Rows().begin(),
            ire = env->problem_.grids_[i].get_Rows().end(),
            icb = env->problem_.grids_[i].get_Columns().begin(),
            ice = env->problem_.grids_[i].get_Columns().end();

        bool flag = true;
        for (ir = irb; ir != ire; ++ir)
            for (ic = icb; ic != ice; ++ic)
            {
                hits_[*ir][*ic] -= 1;
                if (hits_[*ir][*ic] == 0)
                    flag = false;
            }

            return flag;
    }

    template<class E>
    void generate(E* env, uniform_random& rnd)
    {

        for (size_t i = 0; i < grids_set_.size(); ++i)
        {
            grids_set_[i] = 1;
            inc_Hits(env, i);
        }

        changed_ = true;
    }

    TCostType get_Cost() const
    {
        ASSERT_(!changed_);
        return cost_;
    }

    template<class E>
    void evaluate(E* env, uniform_random& rnd)
    {
        if (!changed_)
            return;

        cost_ = 0;
        for (size_t i = 0; i < grids_set_.size(); ++i)
            if (grids_set_[i] == 1) 
                ++cost_;

        changed_ = false;
    }

    void assign(GridMin_Solution const& sol)
    {
        changed_   = sol.changed_;
        cost_      = sol.cost_;
        hits_      = sol.hits_;
        grids_set_ = sol.grids_set_;
    }

    template<class X>
    void copy_To(X& x) const
    {
        x.assign(*this);
    }

    template<class E>
    void print(std::ostream& os, E* env)
    {
        //os << lf;
        //env->problem_.print(os, env);

        os << "Hits:" << lf;
        for (size_t i = 0; i < hits_.size(); ++i)
        {
            for (size_t j = 0; j < hits_[i].size(); ++j)
                os << hits_[i][j] << " ";
            os << lf;
        }

        os << "Cover (" << get_Cost() << "):" << lf;
        for (size_t i = 0; i < grids_set_.size(); ++i)
            if (grids_set_[i] == 1)
                env->problem_.grids_[i].print(os);

        os << lf
            << "cost: " << get_Cost() << lf;
    }

    template<class E>
    static bool read(E* env, std::string const& file_name, Solution_Pool<GridMin_Solution>& pool)
    {
        return false;
    }

    template<class E>
    void write(E* env, std::string const& file_name, size_t id, size_t count)
    {
    }

    template<class V>
    void accept(V& v)
    {
        v(cost_);
        v(changed_);
        v(hits_);
        v(grids_set_);
    }
};
//__________________________________________________________________________________

//EOF!
